/*
 * @lc app=leetcode.cn id=169 lang=cpp
 *
 * [169] 多数元素
 */

// @lc code=start
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        //摩尔投票法
        //n/k就设立k - 1个桶
        //如果与桶里元素相同就计数+1
        //如果与桶里元素都不同，就从桶里各拿出一个
        int n, c = 0;
        for(int i = 0; i < nums.size(); i++){
            if(c == 0) {n = nums[i]; c++;}
            else if (n == nums[i]) c++;
            else c--;
        }
        return n;
    }
};
// @lc code=end

